package J3_14;

public class test {
    //给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
    //
    //算法的时间复杂度应该为 O(log (m+n)) 。
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2,nums1);
        }

        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if ( i != 0 && j != n && nums1[i - 1] > nums2[j]) {
                iMax = i - 1;
            } else if ( j != 0 && i != m && nums1[i] < nums2[j - 1]) {
                iMin = i + 1;
            }else {
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                }else if ( j == 0) {
                    maxLeft = nums1[i - 1];
                } else {
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ( (m + n) % 2 == 1) {
                    return maxLeft;
                }
                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i],nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0;
    }



    //给你一个字符串 s，找到 s 中最长的回文
    //子串
    //。
    //
    //如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
    //
    //

    public String longestPalindrome(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
        char[] ch = s.toCharArray();
        int maxLen = 1;
        int index = 0;
        for (int L = 2; L <= len; L++) {
            for (int i = 0; i < len; i++) {
                int j = L + i - 1;
                if (j >= len) {
                    break;
                }
                if (ch[i] == ch[j]) {
                    if (j - i < 3) {
                        dp[i][j] = true;
                    }else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                }
                if (dp[i][j] && (j - i + 1) > maxLen) {
                    maxLen = j - i + 1;
                    index = i;
                }
            }
        }
        return s.substring(index,index + maxLen);
    }
}
